package com.bauer.base.algorithm.dynamicprogramming;

/**
 * @Author ：rui.wei
 * @Date ：Created in 11:16 2019/8/2
 * @Description：
 */
public class MaxSubString {

    public static int count = 0;

    public static void main(String[] args) {
        char[] charsA = new String("abcdefgh").toCharArray();
        char[] charsB = new String("cabc").toCharArray();
        int[] a = new int[]{0, 0};
        int[] b = new int[]{0, 0};

        calculateMax(charsA, charsB, 0, 0, a);
        calculateMax(charsB, charsA, 0, 0, b);
        System.out.println(a[0] + "----" + a[1]);
        System.out.println(b[0] + "----" + b[1]);

        System.out.println(count);

        System.out.println(maxCommonString(new String("abcdefgh"), new String("cabc")));
    }

    public static void calculateMax(char[] a, char b[], int i, int j, int[] maxLength) {
        if (a.length == i || b.length == j) {
            return;
        }

        int perLength = 0;

        int start = 0;
        boolean preEqual = false;

        for (int k = 0; k + i < a.length && k + j < b.length; k++) {
            count = count+1;
            if (preEqual) {
                if (a[i + k] == b[j + k]) {
                    perLength = 1 + perLength;
                    preEqual = true;
                } else {
                    preEqual = false;
                }
                if (perLength > maxLength[0]) {
                    maxLength[0] = perLength;
                    maxLength[1] = start;
                }

            } else {
                perLength = 0;
                if (a[i + k] == b[j + k]) {
                    start = i + k;
                    perLength = 1 + perLength;
                    preEqual = true;
                    if (perLength > maxLength[0]) {
                        maxLength[0] = perLength;
                        maxLength[1] = start;
                    }
                } else {
                    preEqual = false;
                }
            }
        }

        calculateMax(a, b, i + 1, j, maxLength);
        return;
    }

    public static String maxCommonString(String s1, String s2) {
        String res = "";
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
            return res;
        }
        int max = 0, m = s1.length(), n = s2.length();
        int[][] dp = new int[m][n]; // 定义一个二维数组记录最大公共子串的长度
        // 计算到s1的第i个字符和s2的第j个字符为止的最大公共子串长度
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果s1字符串在i处和s2字符串在j处有字符相同，进入if代码块中
                if (s1.charAt(i) == s2.charAt(j)) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;// 边界的情况
                    } else {
                        dp[i][j] = dp[i - 1][j - 1] + 1;// 加上当前长度
                    }
                    // 记录最大长度和子串
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        res = s1.substring(i - dp[i][j] + 1, i + 1);// substring()左闭右开
                    }
                }
            }
        }
        return res;
    }
}
